package dmsxl.shuzu;

import java.lang.annotation.Target;
import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/6 16:19
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 *
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 */
public class array5_209 {

    public static void main(String[] args) {
//        int[] nums = {2, 3, 1, 2, 4, 3};
        int[] nums = {1, 2, 3, 4, 5};
        int target = 11;
        System.out.println(minSubArrayLen(target, nums));
    }

//    暴力, 超出时间限制
    public static int minSubArrayLen1(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

//    二分查找
    public static int minSubArrayLen2(int target, int[] nums) {
        int length = nums.length;
        int min = Integer.MAX_VALUE;
        int[] sums = new int[length + 1];
        for (int i = 1; i <= length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
//        System.out.println(Arrays.toString(sums));
        for (int i = 0; i <= length; i++) {
            int t = target + sums[i];
            int index = Arrays.binarySearch(sums, t);
            if (index < 0)
                index = ~index;
            if (index <= length) {
                min = Math.min(min, index - i);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

//    滑动窗口/双指针
    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, res = Integer.MAX_VALUE;
        for (int right=0; right<nums.length; right++){
            sum += nums[right];
            while (sum >= target){
                res = Math.min(res, right-left+1);
                sum -= nums[left];
                left += 1;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}
